package com.wfm.leetcode.editor.cn;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * dp[j] 表示以j以前的字符串能在集合中找到
 * [j,i) 左闭右开
 * 比如j=c i=d  那么s1=leet  s2=co
 * leetcode   ["leet","code"]
 *     j i
 * dp[j]我们知道集合里有，所以只要判断substring(j,i)是否集合里有
 *
 */
public class POne39单词拆分{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        // i 定住结尾， j每次从0开始 【j,i）左闭右开
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne39单词拆分().new Solution();
    }
}